1. Field of the Invention
The present invention relates to a mutual division circuit, and more particularly to a mutual division circuit suitable for use in a decoder for decoding error-correcting codes.
2. Description of the Prior Art
Digital signal processing technology for recording and reproducing digital audio and video signals is now in wide use. Encoding and decoding error-correcting codes play an important role in the digital signal processing technology. Error-correcting codes include wide-sense Bose-Chaudhuri-Hocquenghem (BCH) codes, Goppa codes, etc. The principles of the present invention are applicable to these error-correcting codes. However, only the Reed-Solomon code, which is a special form of BCH code, will be referred to in the description which follows.
According to the Reed-Solomon code, the elements of a finite field GF(2.sup.m) (where m is an integer of 1 or more) correspond respectively to symbols. If an irreducible generator polynomial of the finite field, GF(2.sup.m) is represented by G(X) and a root of G(X)=0 by .alpha., then each element or symbol of the finite field GF(2.sup.m) can be expressed by a power of .alpha.. A power .alpha..sup.i (i is an integer) of .alpha. can be represented by a vector in the form of an m-bit binary notation. Vector representations are convenient in digital signal processing.
To encode a Reed-Solomon code, the following parity check matrix H is first defined using the above irreducible generator polynomial .alpha.: ##EQU1## where n indicates the code length and t the number of symbols that can be corrected. If original information is represented by (n-2t) symbols u.sub.0 .about.u.sub.n-2t-1 and parity information by 2t symbols p.sub.0 .about.p.sub.2t-1, then a transmitted code word can be represented by a vector whose elements are n symbols, as follows: EQU f=p.sub.0 P.sub.1. . . p.sub.2t-1 u.sub.0 u.sub.1. . . u.sub.n-2t-1 ].sup.7( 2A)
where [. . . ].sup.t indicates a transposed matrix.
The encoder determines the symbols p.sub.0 .about.p.sub.2t-1 of the parity information such that EQU HF=0 (3)
is satisfied. The transmitted code word f is expressed by a polynomial f(X): EQU f(X)=p.sub.0 +p.sub.1 X+. . . +p.sub.2t-1 X.sup.2t-t +u.sub.0 X.sup.2t +. . . +u.sub.n-2t-1 X.sup.n-1 ( 2B)
When .alpha., .alpha..sup.2, . . . , .alpha..sup.2t are substituted successively for the variables X of the equation (2B), the equation (3) can be expressed as follows: EQU f(.alpha.)=0, f(.alpha..sup.2)=0, . . . , f(.alpha..sup.2t)=0 (4).
If it is assumed that a transmission error e occurs with respect to the transmitted code word f, a received code word r is represented by a vector: EQU r=f+e (5A).
The equation (5A) can be expressed by a polynomial: ##EQU2## When the Reed-Solomon code is used, if the code length represented by n and the number of symbols in the parity information is 2t, then the error can provided the number of error symbols except 0 in the transmission error e is t.
FIG. 1 of the accompanying drawings shows an overall arrangement of a decoder for decoding an error-correcting code. The decoder includes a syndrome generator 1 for generating a syndrome S by multiplying the parity check matrix H represented by the equation (1) by the received code word r. The syndrome S can be expressed by a vector: EQU S=[S.sub.1 S.sub.2. . . S.sub.2t ].sup.t ( 6A),
and by a polynomial: EQU S(X)=S.sub.1 +S.sub.2 X+S.sub.3 X.sup.2 +. . . +S.sub.2t X.sup.2t-1 ( 6B)
Using the respective elements, the syndrome S=Hr is expressed as follows: ##EQU3## The equation (7A) can be expressed by: ##EQU4## If the transmission error e is expressed by a polynomial: e(X)=e.sub.0 X+e.sub.1 X.sup.2 +. . . +e.sub.n-1 X.sup.n-1 and the condition in the encoder according to the equation (4) is used, then the equation (7B) can be expressed as follows: EQU S.sub.j =e(.alpha..sup.j) (j=1, 2, . . . , 2t) (7c).
As shown in FIG. 1, the decoder includes an error locator polynomial deriving circuit 2. The error locator polynomial deriving circuit 2 calculates the coefficients of an error locator polynomial .sigma.(X) and the coefficients of an error evaluator polynomial .omega.(X) from the syndrome polynomial S(X) (actually from the coefficients of the syndrome polynomial S(X)), and supplies the calculated coefficients to an error location detecting circuit 3 and an error pattern calculating circuit 4.
When an error occurs in the jth position as counted from the leading end of the received code word r (i.e., when ej.noteq.0), .alpha..sup.j will be referred to as an error location. If it is assumed that the number of nonzero elements of the transmission error e is .nu. (.nu..ltoreq.t), the error locations of the .nu. nonzero elements (error symbols) are Xi, and error patterns are Y.sub.i (i=1, 2, . . . , .nu.) then .nu. error symbols can be expressed respectively by (X.sub.i, Y.sub.i), and the equation (7C) can be given as follows: ##EQU5## The equation (7D) represents 2t equations with the number of unknowns being 2.nu. (X.sub.i, Y.sub.i) (2.nu..ltoreq.2t). Therefore, these unknowns (X.sub.i, Y.sub.i) can uniquely be determined. In order to easily determine the unknowns (X.sub.i, Y.sub.i) (i=1, 2, . . . , .nu.) which satisfy the equation (7D), the following error locator polynomial .sigma.(X) and error evaluator polynomial .omega.(X) are introduced: ##EQU6##
Since the equation .sigma.(X.sub.i.sup.-1)=0 (i=1, 2, . . . , .sigma.) is satisfied from the equation (8) above, if the coefficients .sigma..sub.i of the error locator polynomial .sigma.(X) can be found, then the error locations X.sub.i (i=1, 2, . . . , .sigma.) can be detected by successively substituting .alpha..sup.-j (j=0, 1, . . . , n-1) in .sigma.(X) and searching for the total number of .alpha..sup.-j when .sigma.(.alpha..sup.-j)=0.
It is known that if an error pattern with respect to an error location X.sub.i is represented by Y.sub.i, then the error pattern Y.sub.i can be calculated, using the error evaluator polynomial .omega.(X), as follows: ##EQU7##
As described later on, the error locator polynomial .sigma.(X) and the error evaluator polynomial .omega.(X) can be derived from the syndrome polynomial S(X) according to the Euclidean division algorithm. The error location detecting circuit 3 shown in FIG. 1 detects an error location X.sub.i from the error locator polynomial .sigma.(X), and generates a digital signal of a high level "1" at the error location and supplies the digital signal to one input terminal of each AND gate of an AND gate group 5. When the error pattern calculating circuit 4 supplies an m-bit binary notation, which is a vector expression of the error pattern Y.sub.i calculated thereby using the equation (10), to the other input terminal of each AND gate of the AND gate group 5 at each error location, the AND gate group 5 generates, in a time-series manner, vector representations of the respective coefficients of the transmission error polynomial e(X) The coefficients of the polynomial r(X) of the received code word are delayed a given period of time by a delay circuit 7. The vector representations of these delayed coefficients and the vector representations of the respective coefficients of the transmission error polynomial e(X) are added to each other by an adder group 6 of mod 2. The adder group 6 now produces the vector representations of the respective coefficients of the polynomial f(X) of the transmitted code word, whose errors have been corrected, based on the fact that addition and subtraction are the same arithmetic operation with mod 2.
One conventional error locator polynomial deriving circuit based on the Euclidean division algorithm will now be described below with reference to FIGS. 2 and 3.
If two polynomials r.sub.-1 (X), r.sub.0 (X) are given and deg (degree) r.sub.0 .ltoreq.deg r.sub.-1, then the following divisions are repeatedly effected according to the Euclidean division algorithm: ##EQU8##
The nonzero r.sub.j (X), by which the polynomials are exactly divided finally, is the greatest common divisor (GCD) of the polynomials r.sub.-1 (X), r.sub.0 (X).
Based on the Euclidean division algorithm, the following theorem is derived: If two polynomials r.sub.-1 (X), r.sub.0 (X) are given, deg r.sub.0 .ltoreq.deg r.sub.-1, and the GCD is h(X), then there exist U(X), V(X) which satisfy: EQU U(X).multidot.r.sub.-1 (X)+V(X).multidot.r.sub.0 (X)=h(X) (12),
and both deg U and deg V are smaller than deg r.sub.-1. In order to determine U(X), V(X), defining EQU U.sub.-1 (X)=0, U.sub.0 (X)=1 (13A) EQU V.sub.-1 (X)=1, V.sub.o (X)=0 (13B)
and using the quotient qi (i=1, 2, . . . , j+1) which are calculated according to the following equations: EQU U.sub.i (X)=q.sub.i (X).multidot.U.sub.i-1 (X)+U.sub.i-2 (X)(14A) EQU V.sub.i (X)=q.sub.i (X).multidot.V.sub.i-1 (X)+V.sub.i-2 (X)(14B).
In this case, (-1).sup.j+1 V.sub.j (X) becomes U(X) and (-1).sup.j U.sub.j (X) becomes V(X).
It is known that using the equations (11A) through (11Z) and the Euclidean division algorithm according to the equations (14A), (14B), the error locator polynomial .sigma.(X) and the error evaluator polynomial .omega.(X) are determined according to an algorithm indicated by steps 100 through 105 shown in FIG. 2, based on the syndrome polynomial S(X) (see the equation (6B))